<!DOCTYPE html>
<html lang="en">
	<head>
		<meta charset="UTF-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1.0" />
		<meta http-equiv="X-UA-Compatible" content="ie=edge" />
		<title>JavaScript 数据结构与算法之美 - 归并排序</title>
	</head>
	<body></body>
	<script>
		const mergeSort = arr => {
			//采用自上而下的递归方法
			const len = arr.length;
			if (len < 2) {
				return arr;
			}
			// length >> 1 和 Math.floor(len / 2) 等价
			let middle = Math.floor(len / 2),
				left = arr.slice(0, middle),
				right = arr.slice(middle); // 拆分为两个子数组
			return merge(mergeSort(left), mergeSort(right));
		};

		const merge = (left, right) => {
			const result = [];

			while (left.length && right.length) {
				// 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
				if (left[0] <= right[0]) {
					result.push(left.shift());
				} else {
					result.push(right.shift());
				}  
			}

			while (left.length) result.push(left.shift());

			while (right.length) result.push(right.shift());

			return result;
		};

		// 测试
		const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
		console.time('归并排序耗时');
		console.log('arr :', mergeSort(arr));
		console.timeEnd('归并排序耗时');
		// arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
		// 归并排序耗时: 0.739990234375ms
	</script>
</html>
